<head>
    <meta charset="UTF-8">
<title>算法提高 The Sky is the Limit</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">Banff<font face="宋体">城雇用了一家广告公司来提升这座城市对潜在的游客的吸引力</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">。其中一个计划中的口号声称延伸在这座城市周围的山脉组成了加拿大最美丽的天际线。但是加拿大消费者保护协会认为&ldquo;最美丽的天际线&rdquo;是一种主观的，无法证实的声称，而且可能因此让人误解。</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">然后那个广告公司就想出了一个口号</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">&ldquo;<font face="Times New Roman">Banff</font><font face="宋体">&mdash;&mdash;加拿大最长的天际线&rdquo;。虽然没有那么引人注意，但这是有希望能证实的，而且这样就能被加拿大复杂的广告法律所接受了。</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">这就是你要介入的原因</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">。广告公司需要的是一个能确定天际线的长度的程序。把每座山脉看作是一个二维的上面两条边长度相等的三角形。一条天际线是一座或多座山脉的轮廓。天际线的长度就是轮廓的总长度。下面的左图显示了三座山脉。右图显示了（用黑线）天际线和（用虚线）山脉上面的边中不是天际线的部分。注意位于山脉之间的地平线部分不在天际线考虑的范围内。</span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><img src="http://lx.lanqiao.cn/RequireFile.do?fid=LaqFramG" width="600" height="176" alt="" /></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; ">&nbsp;</p>
<p>【输入格式】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">第一行包含一个正整数<font face="Times New Roman">N</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">，</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">表示范围内的山脉数</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">。接下来<font face="Times New Roman">N</font><font face="宋体">行每行用三个整数</font><font face="Times New Roman">X,H,B</font><font face="宋体">来描述每一座山脉，分别表示山脉的最高点到某个固定的点的水平距离，山脉的垂直高度和山脉的底边的宽度。每座山脉的底部在同一条水平线上。数据满足</font><font face="Times New Roman">N</font><font face="宋体">&le;</font><font face="Times New Roman">100</font><font face="宋体">，</font><font face="Times New Roman">H</font><font face="宋体">＞</font><font face="Times New Roman">0</font><font face="宋体">而且</font><font face="Times New Roman">B</font><font face="宋体">＞</font><font face="Times New Roman">0</font><font face="宋体">。</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p>【输出格式】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">输出只有一行</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">，</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">即天际线的长度</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">。</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">输出那个长度四舍五入后的结果</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">。</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p>【样例输入】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">3</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">20&nbsp;30&nbsp;35</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">37&nbsp;24&nbsp;29</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">60&nbsp;20&nbsp;13</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p>【样例输出】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">138</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p>【数据规模和约定】</p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">对于</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">20%<font face="宋体">的数据，</font><font face="Times New Roman">1</font><font face="宋体">&le;</font><font face="Times New Roman">N</font><font face="宋体">&le;</font><font face="Times New Roman">5</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">对于</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">50%<font face="宋体">的数据，</font><font face="Times New Roman">1</font><font face="宋体">&le;</font><font face="Times New Roman">N</font><font face="宋体">&le;</font><font face="Times New Roman">30</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>
<p class="p0" style="margin-bottom:0pt; margin-top:0pt; "><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">	</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'Times New Roman'; ">对于</span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">100%<font face="宋体">的数据，</font><font face="Times New Roman">1</font><font face="宋体">&le;</font><font face="Times New Roman">N</font><font face="宋体">&le;</font><font face="Times New Roman">100</font></span><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; "><o:p></o:p></span></p>